/**
 * 给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
 *
 * 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
 *
 * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */

/**
 *dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
 *  *               max( 今天选择 rest,        今天选择 sell       )
 *  *               解释：今天我没有持有股票，有两种可能，我从这两种可能中求最大利润：
 *  *
 *  * 1、我昨天就没有持有，且截至昨天最大交易次数限制为 k；然后我今天选择 rest，所以我今天还是没有持有，最大交易次数限制依然为 k。
 *  *
 *  * 2、我昨天持有股票，且截至昨天最大交易次数限制为 k；但是今天我 sell 了，所以我今天没有持有股票了，最大交易次数限制依然为 k。
 *  * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
 *  *               max( 今天选择 rest,         今天选择 buy         )
 *  *               dp[-1][...][0] = 0
 *  * 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0。
 *  *
 *  * dp[-1][...][1] = -infinity
 *  * 解释：还没开始的时候，是不可能持有股票的。
 *  * 因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
 *  *
 *  * dp[...][0][0] = 0
 *  * 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。
 *  *
 *  * dp[...][0][1] = -infinity
 *  * 解释：不允许交易的情况下，是不可能持有股票的。
 *  * 因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
 */
class MaxProfitFive {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        for(int i=0;i<n;i++) {
            if(i-1==-1) {
                dp[i][0]=0;
                dp[i][1]=-prices[i];
                continue;
            }
            if(i-2==-1) {
                 dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
                 dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
                 continue;
            }
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]);
        }
        return dp[n-1][0];
    }
}